import java.util.Stack;

public class Solution {
    public boolean isValid(String s){
        //1.先创建一个栈
        Stack<Character> stack=new Stack<>();
        //2.挨个遍历字符串，左括号就进栈，右括号就与栈顶元素比较，看是否匹配
        for (int i = 0; i < s.length(); i++) {
          char ch=s.charAt(i);
          //3.此时的字符是左括号
          if (ch=='('||ch=='['||ch=='{'){
              stack.push(ch);
          }
          //4.此时的字符是右括号
          else {
              //4.1 此时的括号是右括号，但是栈是空的
              if (stack.empty()){
                  return false;
              }
              //4.2此时的括号是右括号，栈不是空的，与左括号匹配
              char ch2=stack.peek();//获取当前栈顶元素 ( [ {
              if (ch==')'&&ch2=='('||ch==']'&&ch2=='['||ch=='}'&&ch2=='{'){
                  stack.pop();
              }
              else {
                  return false;
              }
          }
        }
        if (!stack.empty()){
            return false;
        }
        return true;
    }
    //栈的压入，弹出序列
   public boolean IsPopOrder(int []pushV,int []popV){
        Stack<Integer>stack=new Stack<>();
        int j=0;
       for (int i = 0; i < pushV.length; i++) {
           stack.push(pushV[i]);
           while (!stack.empty()&&j< popV.length&&stack.peek()==popV[j]){
               j++;
               stack.pop();
           }
       }
       if (!stack.empty()){
           return false;
       }
       return true;

   }
   //逆波兰表达式求值
    public int evalRPN(String [] tokens){
        //1.先创建一个栈
        Stack <Integer> stack=new Stack<>();
        //2.遍历逆波兰序列
        for (int i = 0; i < tokens.length; i++) {
            String s=tokens[i];
            if (!isOperation(s)){
                //数字
                Integer ret=Integer.valueOf(s);
                stack.push(ret);
            }else {
                int val2=stack.pop();
                int val1=stack.pop();
                switch (s){
                    case "+":
                        stack.push(val1+val2);
                        break;
                    case "-":
                        stack.push(val1-val2);
                        break;
                    case "*":
                        stack.push(val1*val2);
                        break;
                    case "/":
                        stack.push(val1/val2);
                        break;
                }
            }
        }
            return stack.pop();
        }

    private boolean isOperation(String s) {
        if (s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }
        return false;
    }
    //判断字符串是否为回文字符串
    public boolean judge (String str) {
        // write code here
        //先求字符串的长度
        int len=str.length();
        //求i要走几步
        int k=len/2;
        //依次从头，从尾，同时遍历字符串中的每一个字符，在遍历过程中，有一处不符合就立刻返回false,直至把所有字符串遍历完都没有返回false，最后就直接返回true
        for(int i=0;i<k;i++){
            if(str.charAt(i)!=str.charAt(len-1-i)){
                return false;
            }
        }
        return true;
    }
}
